package com.yx.study.leet.primary.math;

import java.util.Arrays;

/**
 * 计数质数
 * 枚举 < 埃氏筛 < 欧式筛（线性筛） < 奇数筛
 * 一般学会埃氏筛过面试就足够了，更深入的还有另外几种算法。
 * Github上Kim Walisch大牛现在已经做到
 * 也就是10的27次方所有的质数和等于这么多。
 * https://leetcode.cn/leetbook/read/top-interview-questions-easy/xnzlu6/
 * */
public class CountPrimes {
    class Solution {

        public int countPrimes(int n) {
            boolean[] isPrim = new boolean[n];
            Arrays.fill(isPrim, true);
            // 从 2 开始枚举到 sqrt(n)。
            for (int i = 2; i * i < n; i++) {
                // 如果当前是素数
                if (isPrim[i]) {
                    // 就把从 i*i 开始，i 的所有倍数都设置为 false。
                    for (int j = i * i; j < n; j+=i) {
                        isPrim[j] = false;
                    }
                }
            }

            // 计数
            int cnt = 0;
            for (int i = 2; i < n; i++) {
                if (isPrim[i]) {
                    cnt++;
                }
            }
            return cnt;
        }
    }
}
